package com.gzl.exercise;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @PROJECT_NAME: exercise
 * @NAME: 数组的度
 * @DESCRIPTION: 简单题
 * @USER: gaozengliang
 * @DATE: 2023/9/11
 */
public class 数组的度 {
    /**
     * 给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。
     *
     * 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [1,2,2,3,1]
     * 输出：2
     * 解释：
     * 输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
     * 连续子数组里面拥有相同度的有如下所示：
     * [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
     * 最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。
     * 示例 2：
     *
     * 输入：nums = [1,2,2,3,1,4,2]
     * 输出：6
     * 解释：
     * 数组的度是 3 ，因为元素 2 重复出现 3 次。
     * 所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。
     *
     *
     * 提示：
     *
     * nums.length 在 1 到 50,000 范围内。
     * nums[i] 是一个在 0 到 49,999 范围内的整数。
     * */
    @Test
    public void findShortestSubArray() {
        int[] nums = {1};
//        int[] nums = {1,2};
//        int[] nums = {1,2,2,3,1};
//        int[] nums = {1,2,2,3,1,4,2};
        if (nums.length<2){
            System.out.println(1);
            return;
        }
        Map<Integer,int[]> maps = new HashMap<>();
        // 遍历数组，统计各个出现的次数及最短子数组长度
        for (int i=0;i<nums.length;i++){
            if (!maps.containsKey(nums[i])) {
                // int[当前出现次数，初始坐标，子数组长度]
                maps.put(nums[i], new int[]{1,i,1});
            }else {
                // int[当前出现次数，初始坐标，子数组长度]
                maps.put(nums[i],new int[]{maps.get(nums[i])[0]+1,maps.get(nums[i])[1],i+1-maps.get(nums[i])[1]});
            }
        }
        int max = 0;
        int mind = 50000;
        // 遍历map，找出出现次数最多的数及数组的度
        for (Map.Entry<Integer, int[]> entry : maps.entrySet()) {
//            System.out.println(entry.getKey() + " " + entry.getValue()[0]+" " + entry.getValue()[1]+" " + entry.getValue()[2]);
            // 如果当前的出现次数多，不必多说，用它的度，如果次数一样，比较度大小
            if (entry.getValue()[0] > max){
                max = entry.getValue()[0];
                mind = entry.getValue()[2];
            }else if (entry.getValue()[0] == max){
                if (mind > entry.getValue()[2]){
                    mind = entry.getValue()[2];
                }
            }
        }
        System.out.println(mind);
//        return mind;
    }
}
